template<class T = int>
struct ScapeGoatTree {
	const double ALPHA = 0.7;
	int head, cnt, ci, top, father, side;
	std::vector<T> key;
	std::vector<int> key_count, ls, rs, size, diff, collect;

	ScapeGoatTree() {}

	ScapeGoatTree(int n) {
		init(n);
	}

	void init(int n) {
		head = cnt = 0;
		key.resize(n + 5, 0);
		key_count.resize(n + 5, 0);
		ls.resize(n + 5, 0);
		rs.resize(n + 5, 0);
		size.resize(n + 5, 0);
		diff.resize(n + 5, 0);
		collect.resize(n + 5, 0);
	}

	void up(int i) {
		size[i] = size[ls[i]] + size[rs[i]] + key_count[i];
		diff[i] = diff[ls[i]] + diff[rs[i]] + (key_count[i] > 0 ? 1 : 0);
	}

	bool balance(int i) {
		return ALPHA * diff[i] >= std::max(diff[ls[i]], diff[rs[i]]);
	}

	void inorder(int i) {
		if(i != 0) {
			inorder(ls[i]);
			if(key_count[i] > 0) {
				collect[++ci] = i;
			}
			inorder(rs[i]);
		}
	}

	int build(int l, int r) {
		if(l > r) {
			return 0;
		}
		int m = (l + r) / 2;
		int h = collect[m];
		ls[h] = build(l, m - 1);
		rs[h] = build(m + 1, r);
		up(h);
		return h;
	}

	void rebuild() {
		if(top != 0) {
			ci = 0;
			inorder(top);
			if(ci > 0) {
				if(father == 0) {
					head = build(1, ci);
				} else if(side == 1) {
					ls[father] = build(1, ci); 
				} else {
					rs[father] = build(1, ci);
				}
			}
		}
	}

	int addOne(T num) {
		key[++cnt] = num;
		ls[cnt] = rs[cnt] = 0;
		key_count[cnt] = size[cnt] = diff[cnt] = 1;
		return cnt;
	}

	void add(int i, int f, int s, T num) {
		if(i == 0) {
			if(f == 0) {
				head = addOne(num);
			} else if(s == 1) {
				ls[f] = addOne(num);
			} else {
				rs[f] = addOne(num);
			}
		} else {
			if(key[i] == num) {
				key_count[i]++;
			} else if(key[i] > num) {
				add(ls[i], i, 1, num);
			} else {
				add(rs[i], i, 2, num);
			}
		}
		up(i);
		if(!balance(i)) {
			top = i;
			father = f;
			side = s;
		}

	}

	void add(T num) {
		top = father = side = 0;
		add(head, 0, 0, num);
		rebuild();
	}

	int small(int i, T num) {
		if(i == 0) {
			return 0;
		}
		if(key[i] >= num) {
			return small(ls[i], num);
		} else {
			return key_count[i] + size[ls[i]] + small(rs[i], num);
		}
	}

	int getRank(T num) {
		return small(head, num) + 1;
	}

	int index(int i, int x) {
		if(size[ls[i]] >= x) {
			return index(ls[i], x);
		} else if(size[ls[i]] + key_count[i] < x) {
			return index(rs[i], x - size[ls[i]] - key_count[i]);
		}
		return key[i];
	}

	int index(int x) {
		return index(head, x);
	}

	T pre(T num) {
		int kth = getRank(num);
		if(kth == 1) {
			return std::numeric_limits<T>::min();
		} else {
			return index(kth - 1);
		}
	}

	T post(T num) {
		int kth = getRank(num + 1);
		if(kth == size[head] + 1) {
			return std::numeric_limits<T>::max();
		} else {
			return index(kth);
		}	
	}

	void remove(int i, int f, int s, T num) {
		if(key[i] == num) {
			key_count[i]--;
		} else if(key[i] > num) {
			remove(ls[i], i, 1, num);
		} else {
			remove(rs[i], i, 2, num);
		}
		up(i);
		if(!balance(i)) {
			top = i;
			father = f;
			side = s;
		}
	}

	void remove(T num) {
		if(getRank(num) != getRank(num + 1)) {
			top = father = side = 0;
			remove(head, 0, 0, num);
			rebuild();
		}
	}

};